<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3061：[Usaco2013 Feb]Partitioning the Farm</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2013 Feb]Partitioning the Farm</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2013 Feb]Partitioning the Farm</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2013 Feb]Partitioning the Farm                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium">&nbsp;Farmer John's farm is divided into an N x N square grid of pastures (2 &lt;= N &lt;= 15). Right now, there is a fence around the outside of the farm, but cows can move freely from pasture to pasture. Farmer John has decided to build fences to separate the cows from each other. Because of zoning laws, each fence must be a horizontal or vertical line going across the entire farm and fences cannot go through pastures. Farmer John only has enough money to build at most K fences (1 &lt;= K &lt;= 2N - 2). Farmer John wants to build the fences in order to minimize the size of the largest resulting group of cows (two cows are in the same group if they can reach each other without going through any fences). Given the current number of cows in each pasture, help Farmer John compute the size of the largest group of cows if he builds the fences optimally. </span></p>
<p></p>
<div style="text-indent: 12pt"><span style="font-size: 12pt">FJ</span><span style="font-size: 12pt">的农场是</span><span style="font-size: 12pt">n*n(2&lt;=n&lt;=15)</span><span style="font-size: 12pt">的，每块地里有若干头牛，</span><span style="font-size: 12pt">FJ</span><span style="font-size: 12pt">最多能建</span><span style="font-size: 12pt">K(1&lt;=k&lt;=2n-2)</span><span style="font-size: 12pt">条篱笆，而这些篱笆只能沿着每块地的边缘建。建完篱笆之后，牛被分成了若干群。</span><span style="font-size: 12pt">FJ</span><span style="font-size: 12pt">想使得这些群中牛最多的那个群的牛尽量少。请输出满足</span><span style="font-size: 12pt">FJ</span><span style="font-size: 12pt">要求的情况下的牛最多的那个群有多少头牛。</span></div></p><hr/><h3>输入格式</h3><p><p><font size="4">* Line 1: Two integers, N and K * Lines 2..1+N: There are N numbers per line, describing the cows in each pasture for one row of the farm (there are at least 0 and at most 1000 cows in each pasture)&nbsp;</font></p></p><hr/><h3>输出格式</h3><p><p><span style="font-size: medium">&nbsp;Line 1: The minimum possible size of the largest group of cows. </span></p></p><hr/><h3>样例输入</h3><pre>3 2
1 1 2
1 1 2
2 2 4
</pre><hr/><h3>样例输出</h3><pre>4 
OUTPUT DETAILS: Farmer John should build fences between columns 2 and 3 and between rows 2 and 3, which creates 4 groups each with 4 cows. </pre><hr/><h3>提示</h3><p><p><img height="119" width="504" alt="" src="../file/3061_0.jpg" /></p></p><hr/><h3>题目来源</h3><p>Gold</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3061" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3061" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>